package leetcode.d_100_199;

public class P129 {
    public static void main(String[] args) {
        P129.Solution solution = new P129().new Solution();
        TreeNode root = new TreeNode(4, new TreeNode(9, new TreeNode(5), new TreeNode(1)), new TreeNode(0));
        System.out.println(solution.sumNumbers(root)); // 1026
    }

    // https://leetcode.cn/problems/sum-root-to-leaf-numbers/
    // 求根节点到叶子节点数字之和
    class Solution {
        public int sumNumbers(TreeNode root) {
            return dfs(root, 0);
        }

        public int dfs(TreeNode node, int preSum) {
            if (node == null) {
                return 0;
            }
            preSum = preSum*10 + node.val;
            if (node.left == null && node.right == null) {
                return preSum;
            }
            int sumLeft = dfs(node.left, preSum);
            int sumRight = dfs(node.right, preSum);
            return sumLeft + sumRight;
        }
    }
}
